#ifndef __TDP2_LINKEDLIST_HPP__
#define __TDP2_LINKEDLIST_HPP__

#include "tdp2.hpp"
#include "tdp2_allocator.hpp"

namespace TDP
{
	namespace Containers
	{
		template<class _T> class Vector;

		template<class _T>
		class ListLink
		{
		protected:
			ListLink<_T> *_prev;
			ListLink<_T> *_next;
			_T _data;

		public:
			ListLink();
			ListLink(const _T &data);

			~ListLink();

			void Link(ListLink<_T> *prev, ListLink<_T> *next);

			_T &Data();
			const _T &Data() const;

			_T *DataPtr();
			const _T *DataPtr() const;

			ListLink<_T> *Previous();
			ListLink<_T> *Next();

			const ListLink<_T> *Previous() const;
			const ListLink<_T> *Next() const;
		};

		template<class _T> class LinkedList
		{
		protected:
			ListLink<_T> *_first;
			ListLink<_T> *_last;
			LargeUInt _numLinks;
			RDX::ObjectManagement::Allocator _alloc;

			ListLink<_T> *CreateLink();
			ListLink<_T> *CreateLink(const _T &base);

		public:
			LinkedList();
			explicit LinkedList(const RDX::ObjectManagement::Allocator &alloc);
			~LinkedList();

			void DeleteLink(ListLink<_T> *l);
			void DeleteLink(const _T *l);
			void DeleteAllLinks();

			ListLink<_T> *CreateLinkAtEnd();
			ListLink<_T> *CreateLinkAtStart();
			ListLink<_T> *CreateLinkAfter(ListLink<_T> *l);
			ListLink<_T> *CreateLinkBefore(ListLink<_T> *l);

			ListLink<_T> *CreateLinkAtEnd(const _T &base);
			ListLink<_T> *CreateLinkAtStart(const _T &base);
			ListLink<_T> *CreateLinkAfter(ListLink<_T> *l, const _T &base);
			ListLink<_T> *CreateLinkBefore(ListLink<_T> *l, const _T &base);

			ListLink<_T> *Find(const _T &cmp);
			ListLink<_T> *Find(const _T *cmp);
			ListLink<_T> *First();
			const ListLink<_T> *First() const;
			ListLink<_T> *Last();
			const ListLink<_T> *Last() const;

			void Flatten(Vector<_T> &v);
			LargeUInt NumLinks() const;
		};
	};
};

namespace TDP
{
	namespace Containers
	{
		template <class _T>
		inline ListLink<_T>::ListLink()
		{
			_prev = _next = NULL;
		}

		template <class _T>
		inline ListLink<_T>::ListLink(const _T &data)
		{
			_prev = _next = NULL;
			_data = data;
		}

		template <class _T>
		inline ListLink<_T>::~ListLink()
		{
			if(_prev)
				_prev->_next = _next;
			if(_next)
				_next->_prev = _prev;
		}

		template <class _T>
		inline void ListLink<_T>::Link(ListLink<_T> *prev, ListLink<_T> *next)
		{
			_prev = prev;
			_next = next;

			if(prev)
				prev->_next = this;
			if(next)
				next->_prev = this;
		}

		template <class _T>
		inline _T &ListLink<_T>::Data()
		{
			return _data;
		}

		template <class _T>
		inline const _T &ListLink<_T>::Data() const
		{
			return _data;
		}

		template <class _T>
		inline _T *ListLink<_T>::DataPtr()
		{
			return &_data;
		}

		template <class _T>
		inline const _T *ListLink<_T>::DataPtr() const
		{
			return &_data;
		}

		template <class _T>
		inline ListLink<_T> *ListLink<_T>::Previous()
		{
			return _prev;
		}

		template <class _T>
		inline ListLink<_T> *ListLink<_T>::Next()
		{
			return _next;
		}

		template <class _T>
		inline const ListLink<_T> *ListLink<_T>::Previous() const
		{
			return _prev;
		}

		template <class _T>
		inline const ListLink<_T> *ListLink<_T>::Next() const
		{
			return _next;
		}

		template <class _T>
		inline LinkedList<_T>::LinkedList()
			: _first(NULL), _last(NULL), _alloc(TDP::Memory::DefaultAllocator()), _numLinks(0)
		{
		}

		template <class _T>
		inline LinkedList<_T>::LinkedList(const RDX::ObjectManagement::Allocator &alloc)
		{
			_first = _last = NULL;
			_alloc = alloc;
			_numLinks = 0;
		}


		template <class _T>
		inline LinkedList<_T>::~LinkedList()
		{
			DeleteAllLinks();
		}

		template <class _T>
		inline void LinkedList<_T>::DeleteAllLinks()
		{
			ListLink<_T> *current;
			ListLink<_T> *next;

			current = _first;
			while(current)
			{
				next = current->Next();
				current->~ListLink<_T>();
				_alloc.Realloc(current, 0);
				current = next;
			}
			_first = _last = NULL;
			_numLinks = 0;
		}

		template <class _T>
		inline void LinkedList<_T>::DeleteLink(ListLink<_T> *l)
		{
			if(_first == l)
				_first = l->Next();
			if(_last == l)
				_last = l->Previous();
			_numLinks--;
			l->~ListLink<_T>();
			_alloc.Free(l);
		}

		template <class _T>
		inline void LinkedList<_T>::DeleteLink(const _T *cmp)
		{
			terListLink<_T> *l;

			l = _first;
			while(l)
			{
				l = l->Next();
				if(l->DataPtr() == cmp)
				{
					this->DeleteLink(l);
					return;
				}
			}
		}

		template <class _T>
		inline ListLink<_T> *LinkedList<_T>::CreateLink()
		{
			ListLink<_T> *newLink = _alloc.Realloc<ListLink<_T>>(NULL, 1);
			if(!newLink)
				return NULL;

			try
			{
				new (newLink) ListLink<_T>();
			}
			catch(...)
			{
				_alloc.Realloc(newLink, 0);
				throw;
			}
			return newLink;
		}

		template<class _T>
		ListLink<_T> *LinkedList<_T>::CreateLink(const _T &base)
		{
			ListLink<_T> *newLink = _alloc.CAlloc<ListLink<_T>>(1);
			if(!newLink)
				return NULL;

			try
			{
				new (newLink) ListLink<_T>(base);
			}
			catch(...)
			{
				newLink->~ListLink<_T>();
				_alloc.Free(newLink);
				throw;
			}
			return newLink;
		}

		template <class _T>
		inline ListLink<_T> *LinkedList<_T>::CreateLinkAtEnd()
		{
			ListLink<_T> *newLink = CreateLink();
			if(!newLink)
				return NULL;

			newLink->Link(_last, NULL);
			_numLinks++;

			if(!_last)
				_first = newLink;
			_last = newLink;

			return newLink;
		}

		template <class _T>
		inline ListLink<_T> *LinkedList<_T>::CreateLinkAtStart()
		{
			terListLink<_T> *newLink = CreateLink();
			if(!newLink)
				return NULL;

			newLink->Link(NULL, _first);
			_numLinks++;

			if(!_first)
				_last = newLink;
			_first = newLink;

			return newLink;
		}

		template <class _T>
		inline ListLink<_T> *LinkedList<_T>::CreateLinkAfter(ListLink<_T> *l)
		{
			ListLink<_T> *newLink = CreateLink();
			if(!newLink)
				return NULL;

			newLink->Link(l, l->Next());
			_numLinks++;

			return newLink;
		}

		template <class _T>
		inline ListLink<_T> *LinkedList<_T>::CreateLinkBefore(ListLink<_T> *l)
		{
			terListLink<_T> *newLink = CreateLink();
			if(!newLink)
				return NULL;

			newLink->Link(l->Prev(), l);
			_numLinks++;

			return newLink;
		}

		template <class _T>
		inline ListLink<_T> *LinkedList<_T>::CreateLinkAtEnd(const _T &base)
		{
			terListLink<_T> *newLink = CreateLink();
			if(!newLink)
				return NULL;

			newLink->Link(_last, NULL);
			_numLinks++;

			if(!_last)
				_first = newLink;
			_last = newLink;

			return newLink;
		}

		template <class _T>
		inline ListLink<_T> *LinkedList<_T>::CreateLinkAtStart(const _T &base)
		{
			terListLink<_T> *newLink = CreateLink(base);
			if(!newLink)
				return NULL;

			newLink->Link(NULL, _first);
			_numLinks++;

			if(!_first)
				_last = newLink;
			_first = newLink;

			return newLink;
		}

		template <class _T>
		inline ListLink<_T> *LinkedList<_T>::CreateLinkAfter(ListLink<_T> *l, const _T &base)
		{
			terListLink<_T> *newLink = CreateLink(base);
			if(!newLink)
				return NULL;

			newLink->Link(l, l->Next());
			_numLinks++;

			return newLink;
		}

		template <class _T>
		inline ListLink<_T> *LinkedList<_T>::CreateLinkBefore(ListLink<_T> *l, const _T &base)
		{
			terListLink<_T> *newLink = CreateLink(base);
			if(!newLink)
				return NULL;

			newLink->Link(l->Prev(), l);
			_numLinks++;

			return newLink;
		}


		template <class _T>
		inline ListLink<_T> *LinkedList<_T>::Find(const _T &cmp)
		{
			terListLink<_T> *l;

			l = _first;
			while(l)
			{
				l = l->Next();
				if(l->Data() == cmp)
					return l;
			}

			return NULL;
		}

		template <class _T>
		inline ListLink<_T> *LinkedList<_T>::Find(const _T *cmp)
		{
			terListLink<_T> *l;

			l = _first;
			while(l)
			{
				l = l->Next();
				if(l->DataPtr() == cmp)
					return l;
			}

			return NULL;
		}

		template <class _T>
		inline ListLink<_T> *LinkedList<_T>::First()
		{
			return _first;
		}

		template <class _T>
		inline const ListLink<_T> *LinkedList<_T>::First() const
		{
			return _first;
		}

		template <class _T>
		inline ListLink<_T> *LinkedList<_T>::Last()
		{
			return _last;
		}

		template <class _T>
		inline const ListLink<_T> *LinkedList<_T>::Last() const
		{
			return _last;
		}

		template <class _T>
		inline void LinkedList<_T>::Flatten(Vector<_T> &v)
		{
			ListLink<_T> *l;

			l = _first;

			v.Alloc(_numLinks);
			for(LargeUInt i=0;i<_numLinks;i++)
			{
				v[i] = l->Data();
				l = l->Next();
			}
		}

		template <class _T>
		inline LargeUInt LinkedList<_T>::NumLinks() const
		{
			return _numLinks;
		}
	};
};

#endif
